'''
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,3]
 * 输出: 3
 * 示例 2:
 *
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 * 通过次数163,596提交次数258,919
 *
'''

from collections import defaultdict
import math
class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1

        for i in hash_table:
            if hash_table[i] >= math.ceil(len(nums)/2):
                return i

'''
思路：
1、遍历 nums 中的所有元素并建立键/值对，并统计每个值出现的次数；
2、返回出现次数大于(n\2)的元素。

结果：
执行用时 :60 ms
内存消耗 :15 MB

'''